package com.ruoxi.blog.test;

import java.util.Arrays;

/**
	* @author YaoXian
	* @title: GuiSort
	* @projectName ruoxi-blog
	* @description: 若兮微服务 - 归并排序
	* @date 2021-03-23 14:59
	*/
public class GuiSort {
		public static void main(String[] args) {
				int [] arr= {2,4,8,1,7,5,3,6};
				int [] temp = new int[arr.length];
				split(arr,0,arr.length - 1,temp);
				System.out.println(Arrays.toString(arr));
		}
		
		public static void split(int [] arr,int left,int right,int [] temp){
				if (left < right){
						int middle = (left+right)/2;
						//向左递归拆分
						split(arr,left,middle,temp);
						//向右递归拆分
						split(arr,middle+1,right,temp);
						//每左右拆分一次就合并一次
						merge(arr,left,middle,right,temp);
				}
		}
		
		public static void merge(int [] arr,int left,int middle,int right,int [] temp){
				int i = left;
				int j = middle + 1;
				int t = 0;
				while (i<=middle && j<=right){
						if (arr[i] <= arr[j]){
								temp[t] = arr[i];
								i++;
						}else {
								temp[t] = arr[j];
								j++;
						}
						t++;
				}
				
				while (i<=middle){
						temp[t] = arr[i];
						i++;
						t++;
				}
				
				while (j<=right){
						temp[t] = arr[j];
						j++;
						t++;
				}
				t = 0;
				int tempLeft = left; //
				//第一次合并 tempLeft = 0 , right = 1 //  tempLeft = 2  right = 3 // tL=0 ri=3
				//最后一次 tempLeft = 0  right = 7
				while(tempLeft <= right) {
						arr[tempLeft] = temp[t];
						t += 1;
						tempLeft += 1;
				}
		}
}
